/***************************************************************************
 *            solve.c
 *
 *  Tue Aug 30 17:36:22 2005
 *  Copyright  2005  Yitzhak Grossman
 *  celejar@gmail.com
 ****************************************************************************/

/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
 

/* core solving logic for sudoku solver - originally written for solver and
 * borrowed (modified) for use in generator
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WII
#ifndef WII
#include "../include/sudoku.h"
#else
#include "sudoku.h"
#endif

int solve(struct sudoku_info *sudoku)
{
	int i, j, value;
	struct sudoku_info new_sudoku1, new_sudoku2;
	//~ printf("%d\n", sudoku->known);
	memcpy(&new_sudoku1, sudoku, sizeof(struct sudoku_info));
	if (add_cells(&new_sudoku1)) {/* printf("poppping\n"); */ return 1;}
	if (Solutions == 2) return 0;
	memcpy(sudoku, &new_sudoku1, sizeof(struct sudoku_info));
	find_assume(&new_sudoku1, &i, &j, &value);
	//~ for (z = 0; z < sudoku->assume; z++) printf(" ");
	//~ printf("Assuming %d at %d, %d\n", value, i, j);
	if (!set_cell(&new_sudoku1, i, j, value))
	{
		memcpy(&new_sudoku2, &new_sudoku1, sizeof(struct sudoku_info));
		//~ new_sudoku2.assume++;
		solve(&new_sudoku2);
		if (Solutions == 2) return 0;
	}
	//~ for (z = 0; z < sudoku->assume; z++) printf(" ");
	//~ printf("Assuming NOT %d at %d, %d\n", value, i, j);
	memcpy(&new_sudoku1, sudoku, sizeof(struct sudoku_info));
	new_sudoku1.info[i][j][value - 1] = NO;
	//~ new_sudoku1.assume++;
	solve(&new_sudoku1);
	if (Solutions == 2) return 0;
	//~ printf("poppping\n");
	return 0;
}
void find_assume(struct sudoku_info *sudoku, int *i, int *j, int *value)
{
	int k, l, m, counter, most = -1;
	for (k = 0; k < 9; k++)
		for (l = 0; l < 9; l++)
		{
			if (sudoku->grid[k][l]) continue;
			counter = 0;
			for (m = 0; m < 9; m++)
				if (sudoku->info[k][l][m] == NO) counter++;
			if (counter > most)
			{
				*i = k;
				*j = l;
				most = counter;
			}
		}
	for (k = 0; k < 9; k++)
		if (sudoku->info[*i][*j][k] == MAYBE) {*value = k + 1; break;}
}
